package com.algrithom.dfs;

/**
 * 剑指 Offer II 116. 朋友圈
 */
public class Solution1 {
    
    public static void main(String[] args){
        // int[][] isConnected = new int[][] { { 1, 1, 0 }, { 1, 1, 0 }, { 0, 0, 1 } };
        int[][] isConnected = new int[][]{{1,0,0,1},{0,1,1,0},{0,1,1,1},{1,0,1,1}};
        Solution1 solution1 = new Solution1();
        System.out.println(solution1.findCircleNum(isConnected));
    }
    
    public int findCircleNum(int[][] isConnected){
        int rowLen = isConnected.length;
        int count = 0;
        boolean[] visited = new boolean[rowLen];
        for (int i = 0; i < rowLen; i++) {
            for (int j = 0; j < rowLen; j++) {
                if (!visited[i]) {
                    dfs(isConnected,visited,i);
                    count++;
                }
            }
        }
        return count;
    }
    
    private void dfs(int[][] isConnect,boolean[] visited,int index){
        int len = isConnect.length;
        visited[index] = true;
        for (int k = 0; k < len; k++) {
            if (isConnect[index][k] == 1 && !visited[k]) {
                dfs(isConnect,visited,k);
            }
        }
    }
}
